ArrayList = ArrayList or {}

function ArrayList.new()
    local inst = {
        _cname = "lang.ArrayList"
    }
    
    local arr = {}
    local len = 0
    
    function inst:count()
        return len
    end
    
    function inst:get(index)
        assert(index >= 1 and index <= len, "get: out of range")
        return arr[index]
    end
    
    function inst:add(v)
        len = len + 1
        arr[len] = v
    end
    
    function inst:addAll(tb)
        if "lang.ArrayList" == tb._cname then
            local len = tb:count()
            for i=1,len do
                self:add(tb[i])
            end
            return
        end
        
        for k, v in pairs(tb) do
            self:add(v)
        end
    end
    
    function inst:insert(index, v)
        assert("number" == type(index), "insert: index not number")
        assert(index >= 1 and index <= len + 1, "insert: out of range")
        if index <= len then --在中间或开头插入
            for i=len,index,-1 do
                arr[i+1] = arr[i]
            end
        end
        arr[index] = v
        len = len + 1
    end
    
    function inst:indexOf(v)
        for i=1,len do
            if arr[i] == v then
                return i
            end
        end
        return -1
    end
    
    function inst:lastIndexOf(v)
        for i=len,1 do
            if arr[i] == v then
                return len - i + 1
            end
        end
        return -1
    end
    
    function inst:contains(v)
        return -1 ~= self:indexOf(v)
    end
    
    function inst:find(matchFunc)
        for i=1,len do
            if matchFunc(i, arr[i]) then
                return i, arr[i]
            end
        end
        return -1, nil
    end
    
    function inst:findLast(matchFunc)
        for i=len,1,-1 do
            if matchFunc(i, arr[i]) then
                return i, arr[i]
            end
        end
        return -1, nil
    end
    
    function inst:findAll(matchFunc)
        local list = ArrayList.new()
        for i=1,len do
            if matchFunc(arr[i], i) then
                list:add(arr[i])
            end
        end
        return list
    end
    
    function inst:removeFirst()
        if 0 == len then return nil end
        local ret = arr[1]
        table.remove(arr, 1)
        len = len - 1
        return ret
    end
    
    function inst:removeLast()
        if 0 == len then return nil end
        local ret = arr[len]
        arr[len] = nil
        len = len - 1
        return ret
    end
    
    function inst:removeAt(index)
        assert("number" == type(index), "removeAt: index not number")
        if 0 == len then return nil end
        assert(index >= 1 and index <= len, "removeAt: out of range")
        local ret = arr[index]
        if index == len then --删除尾部元素
            arr[index] = nil
        else
            table.remove(arr, index)
        end
        len = len - 1
        return ret
    end
    
    function inst:removeRange(index, count)
        assert(index >= 1 and index <= len, "removeRange: out of range: " .. index)
        local index2 = index + count
        
        if index2 > len then --删除尾部的n个元素
            for i=index,len do
                arr[i] = nil
            end
            len = index - 1
        else --删除中间或开头的n个元素
            local j = index
            for i=index2,len do --尾部的元素往前填充
                arr[j] = arr[i]
                j = j + 1
            end
            for i=j,len do
                arr[i] = nil
            end
            len = len - count
        end
    end
    
    function inst:remove(v)
        local index = self:indexOf(v)
        if -1 ~= index then
            self:removeAt(index)
        end
        return index
    end
    
    function inst:clear()
        for i=1,len do
            arr[i] = nil
        end
        len = 0
    end
    
    function inst:sort(sortFunc)
        table.sort(arr, sortFunc)
    end
    
    function inst:reverse()
        local i = 1
        local j = len
        while i < j - 1 do
            local temp = arr[i]
            arr[i] = arr[j]
            arr[j] = temp
            i = i + 1
            j = j - 1
        end
    end
    
    function inst:shift()
        error("shift: not impl")
    end

    function inst:__tostring()
        if 0 == len then return "" end
        local strTb = {}
        for i=1,len do
            local item = arr[i]
			table.insert(strTb, (nil == item) and "nil" or tostring(item))
        end
        return table.concat(strTb, ",")
    end

	function inst:__len()
		return len
	end
    
    function inst:__index(k) --访问不存在的成员, 只允许: [num]
        local keyType = type(k)
        if "number" == keyType then
            assert(k >= 1 and k <= len, "out of range: " .. k)
            return arr[k]
        end
        error("ArrayList: invalid member: " .. k)
    end
    
    function inst:__newindex(k, v) --设置不存在的成员, 只允许: [num] = v
        assert("number" == type(k), "ArrayList: add member error: " .. k)
        arr[k] = v
    end

    setmetatable(inst, inst)
    return inst
end


local function Test1()
    local list = ArrayList.new()
    assert(0 == list:count(), "count error")
    assert(-1 == list:indexOf("c"), "indexOf error")
    assert(false == list:contains("c"), "contains error")

    list:add("a")
    assert(1 == list:count(), "add error")
    assert(1 == list:indexOf("a"), "add error")
    assert(list:contains("a"), "add error")
    list:add("a")
    assert(2 == list:count(), "add error")
    assert(1 == list:indexOf("a"), "add error")
    list:add("b")
    assert(list:contains("b"), "add error")
    assert(3 == list:indexOf("b"), "add error")
    list:add("c")
    list:add("d")
    list:add("e")
    assert(6 == list:indexOf("e"), "add error")
    assert(6 == list:count(), "add error")

    assert("a" == list:removeFirst(), "removeFirst error")
    assert(list:contains("a"), "removeFirst error")
    assert(5 == list:count(), "removeFirst error")
    assert(1 == list:indexOf("a"), "add error")
    assert("a" == list:removeFirst(), "removeFirst error")
    assert(false == list:contains("a"), "removeFirst error")
    assert(4 == list:count(), "removeFirst error")
    assert(1 == list:indexOf("b"), "add error")
    assert("e" == list:removeLast(), "removeFirst error")
    assert("d" == list:removeLast(), "removeFirst error")
    assert(2 == list:count(), "removeFirst error")
    assert("b" == list[1], "insert error")
    assert("c" == list[2], "insert error")

    list:insert(1, "a")
    list:insert(2, "b")
    assert(4 == list:count(), "insert error")
    assert("a" == list[1], "insert error")
    assert("b" == list[2], "insert error")
    assert("b" == list[3], "insert error")
    assert("c" == list[4], "insert error")

    list:insert(list:count(), "d")
    assert(5 == list:count(), "insert error")
    assert("a" == list[1], "insert error")
    assert("b" == list[2], "insert error")
    assert("b" == list[3], "insert error")
    assert("d" == list[4], "insert error")
    assert("c" == list[5], "insert error")

    list:insert(list:count() + 1, "e")
    assert(6 == list:count(), "insert error")
    assert("a" == list[1], "insert error")
    assert("b" == list[2], "insert error")
    assert("b" == list[3], "insert error")
    assert("d" == list[4], "insert error")
    assert("c" == list[5], "insert error")
    assert("e" == list[6], "insert error")

    list:removeRange(5, 2)
    assert(4 == list:count(), "removeRange error")
    assert("a" == list[1], "removeRange error")
    assert("b" == list[2], "removeRange error")
    assert("b" == list[3], "removeRange error")
    assert("d" == list[4], "removeRange error")

    list:removeRange(2, 2)
    assert(2 == list:count(), "removeRange error")
    assert("a" == list[1], "removeRange error")
    assert("d" == list[2], "removeRange error")

    list[2] = "b"
    list:add("c")
    list:add("d")
    list:add("e")
    assert(5 == list:count(), "add error")
    list:removeAt(1)
    assert(4 == list:count(), "removeAt error")
    assert(false == list:contains("a"), "removeRange error")
    assert("b" == list[1], "removeAt error")
    assert("c" == list[2], "removeAt error")
    assert("d" == list[3], "removeAt error")
    assert("e" == list[4], "removeAt error")
    list:removeAt(list:count())
    assert(3 == list:count(), "removeAt error")
    assert(false == list:contains("a"), "removeAt error")
    assert(true == list:contains("b"), "removeAt error")
    assert("b" == list[1], "removeAt error")
    assert("c" == list[2], "removeAt error")
    assert("d" == list[3], "removeAt error")
    assert(false == list:contains("e"), "removeAt error")
    list:removeAt(2)
    assert(2 == list:count(), "removeAt error")
    assert("b" == list[1], "removeAt error")
    assert("d" == list[2], "removeAt error")
    assert(false == list:contains("c"), "removeAt error")

    list:clear()
    assert(0 == list:count(), "clear error")
    assert(-1 == list:indexOf("a"), "clear error")
    assert(-1 == list:indexOf("b"), "clear error")
    assert(false == list:contains("b"), "clear error")

    list:add("a")
    list:add("b")
    list:add("c")
    list:reverse()
    assert(3 == list:count(), "reverse error")
    assert("c" == list[1], "reverse error")
    assert("b" == list[2], "reverse error")
    assert("a" == list[3], "reverse error")
end

local function TestAddAll()
    local list = ArrayList.new()

    list:add("a")
    list:add("b")

    local list2 = ArrayList.new()

    list2:add("one")
    list2:add("two")

    list:addAll(list2)
    assert(4 == list:count(), "addAll error")
    print("tostring: " .. tostring(list))

    local tb = {"c", "d", "e"}
    list:addAll(tb)
    assert(7 == list:count(), "addAll error")
    print("tostring: " .. tostring(list))
end

Test1()
